﻿#include <iostream>
using namespace std;
#include <vector>
//class Solution
//{
//	bool vis[16][16];
//	int dx[4] = { 0, 0, 1, -1 };
//	int dy[4] = { 1, -1, 0, 0 };
//	int m, n;
//	int ret;
//public:
//	int getMaximumGold(vector<vector<int>>& g)
//	{
//		m = g.size(), n = g[0].size();
//		for (int i = 0; i < m; i++)
//			for (int j = 0; j < n; j++)
//			{
//				if (g[i][j])
//				{
//					vis[i][j] = true;
//					dfs(g, i, j, g[i][j]);
//					vis[i][j] = false;
//				}
//			}
//		return ret;
//	}
//	void dfs(vector<vector<int>>& g, int i, int j, int path)
//	{
//		ret = max(ret, path);
//		for (int k = 0; k < 4; k++)
//		{
//			int x = i + dx[k], y = j + dy[k];
//			if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && g[x][y])
//			{
//				vis[x][y] = true;
//				dfs(g, x, y, path + g[x][y]);
//				vis[x][y] = false;
//			}
//		}
//	}
//};////////class Solution
//{
//	int dx[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
//	int dy[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
//	int m, n;
//public:
//	void dfs(vector<vector<char>>& board, int i, int j)
//	{
//		// 统计⼀下周围的地雷个数
//		int count = 0;
//		for (int k = 0; k < 8; k++)
//		{
//			int x = i + dx[k], y = j + dy[k];
//			if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M')
//			{
//				count++;
//			}
//		}//		if (count) // 周围有地雷
//		{
//			board[i][j] = count + '0';
//			return;//		}
//		else // 周围没有地雷
//		{
//			board[i][j] = 'B';
//			for (int k = 0; k < 8; k++)
//			{
//				int x = i + dx[k], y = j + dy[k];
//				if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
//				{
//					dfs(board, x, y);
//				}
//			}
//		}//	}//
//	vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>&
//		click)
//	{
//		m = board.size(), n = board[0].size();
//		int x = click[0], y = click[1];
//		if (board[x][y] == 'M') // 直接点到地雷
//		{
//			board[x][y] = 'X';
//			return board;
//		}
//		dfs(board, x, y);
//		return board;
//	}
//};
//
//
//class Solution
//{
//	int dx[4] = { 0,0,1,-1 };
//	int dy[4] = { 1,-1,0,0 };
//	int r, c;
//	bool check[101][101];
//	int count;
//public:
//	bool flag(int x, int y, int k)
//	{
//		int tmp = 0;
//		while (x)
//		{
//			tmp += x % 10;
//			x /= 10;
//		}
//		while (y)
//		{
//			tmp += y % 10;
//			y /= 10;
//		}
//		return tmp <= k;
//	}
//	void dfs(int i, int j, int k)
//	{
//		count++;
//		check[i][j] = true;
//		for (int l = 0; l < 4; l++)
//		{
//			int x = i + dx[l], y = j + dy[l];
//			if (x >= 0 && x < r && y >= 0 && y < c && !check[x][y] && flag(x, y, k))
//			{
//				dfs(x, y, k);
//			}
//		}
//	}
//	int wardrobeFinishing(int m, int n, int cnt)
//	{
//		r = m, c = n;
//		dfs(0, 0, cnt);
//		return count;
//	}
//};
//
//
//class Solution
//{
//
//public:
//	int dfs(int n, vector<int>& check)
//	{
//		if (check[n] != -1)
//		{
//			return check[n];
//		}
//		if (n == 0 || n == 1)
//		{
//			check[n] = n;
//			return n;
//		}
//		check[n] = dfs(n - 1, check) + dfs(n - 2, check);
//		return check[n];
//	}
//	int fib(int n)
//	{
//		vector<int> check(31, -1);
//		return dfs(n, check);
//	}
//};
//
//
//class Solution {
//public:
//	int minCostClimbingStairs(vector<int>& cost) {
//		int n = cost.size();
//		vector<int> dp(n + 1, 0);
//		dp[0] = dp[1] = 0;
//		for (int i = 2; i < n + 1; i++)
//		{
//			dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);
//		}
//		return dp[n];
//
//	}
//};
//
//
//class Solution {
//public:
//	int numDecodings(string s)
//	{
//		int n = s.size();
//		vector<int> dp(n + 1);
//		dp[0] = s[0] != '0' ? 1 : 0;
//		if (n == 1)
//		{
//			return dp[0];
//		}
//		if (s[1] >= '1' && s[1] <= '9')
//		{
//			dp[1] = dp[0];
//		}
//		else
//		{
//			dp[0] = 0;
//		}
//		int tmp = s[0] - '0';
//		tmp = tmp * 10 + (s[1] - '0');
//		if (tmp >= 10 && tmp <= 26)
//		{
//			dp[1] += 1;
//		}
//		for (int i = 2; i < n; i++)
//		{
//			if (s[i] >= '1' && s[i] <= '9')
//			{
//				dp[i] = dp[i - 1];
//			}
//			int tmp = s[i - 1] - '0';
//			tmp = tmp * 10 + (s[i] - '0');
//			if (tmp >= 10 && tmp <= 26)
//			{
//				dp[i] += dp[i - 2];
//			}
//		}
//		return dp[n - 1];
//	}
//};
//
//// 不同路径
//// https://leetcode.cn/problems/unique-paths/
//class Solution
//{
//public:
//	int uniquePaths(int m, int n)
//	{
//		vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//		dp[0][1] = 1;
//		for (int i = 1; i <= m; i++)
//		{
//			for (int j = 1; j <= n; j++)
//			{
//				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//			}
//		}
//		return dp[m][n];
//	}
//};
//
//// 不同路径Ⅱ
//// https://leetcode.cn/problems/unique-paths-ii/
//class Solution {
//public:
//	int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
//	{
//		int n = obstacleGrid.size(), m = obstacleGrid[0].size();
//		vector<vector<int>> dp(n + 1, vector<int>(m + 1));
//		dp[0][1] = 1;
//		for (int i = 1; i <= n; i++)
//		{
//			for (int j = 1; j <= m; j++)
//			{
//				if (obstacleGrid[i - 1][j - 1] == 0)
//				{
//					dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//				}
//			}
//		}
//		return dp[n][m];
//
//	}
//};
//
//
//// 珠宝的最高价值
//// https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/
//class Solution {
//public:
//	int jewelleryValue(vector<vector<int>>& frame)
//	{
//		int n = frame.size(), m = frame[0].size();
//		vector<vector<int>> dp(n + 1, vector<int>(m + 1));
//		for (int i = 1; i <= n; i++)
//		{
//			for (int j = 1; j <= m; j++)
//			{
//				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
//			}
//		}
//		return dp[n][m];
//	}
//};
//
//
//// 下降路径最小和
//// https://leetcode.cn/problems/minimum-falling-path-sum/
//class Solution {
//public:
//	int minFallingPathSum(vector<vector<int>>& matrix)
//	{
//		int n = matrix.size();
//		vector<vector<int>> dp(n + 1, vector<int>(n + 2));
//		for (int i = 1; i <= n; i++)
//		{
//			dp[i][0] = INT_MAX;
//			dp[i][n + 1] = INT_MAX;
//		}
//		for (int i = 1; i <= n; i++)
//		{
//			for (int j = 1; j <= n; j++)
//			{
//				dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
//			}
//		}
//		int Min = dp[n][n];
//		for (int i = 1; i < n; i++)
//		{
//			Min = min(Min, dp[n][i]);
//		}
//		return Min;
//
//	}
//};
//
//
//
//// 最小路径和
//// https://leetcode.cn/problems/minimum-path-sum/
//class Solution
//{
//public:
//	int minPathSum(vector<vector<int>>& grid)
//	{
//		int n = grid.size(), m = grid[0].size();
//		vector<vector<int>> dp(n + 1, vector<int>(m + 1));
//		for (int i = 0; i <= m; i++)
//		{
//			dp[0][i] = INT_MAX;
//		}
//		for (int i = 2; i <= n; i++)
//		{
//			dp[i][0] = INT_MAX;
//		}
//
//		for (int i = 1; i <= n; i++)
//		{
//			for (int j = 1; j <= m; j++)
//			{
//				dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i - 1][j - 1];
//			}
//		}
//		return dp[n][m];
//	}
//};
//
//
//// 地下城游戏
//// https://leetcode.cn/problems/dungeon-game/
//class Solution
//{
//public:
//	int calculateMinimumHP(vector<vector<int>>& dungeon)
//	{
//		int m = dungeon.size(), n = dungeon[0].size();
//		vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
//		dp[m][n - 1] = 1, dp[m - 1][n] = 1;
//
//		for (int i = m - 1; i >= 0; i--)
//		{
//			for (int j = n - 1; j >= 0; j--)
//			{
//				dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
//				dp[i][j] = max(1, dp[i][j]);
//			}
//		}
//		return dp[0][0];
//	}
//};
//
//
//// https://leetcode.cn/problems/the-masseuse-lcci/
//// 按摩师
//class Solution
//{
//public:
//	int massage(vector<int>& nums)
//	{
//		int n = nums.size();
//		if (n == 0)
//		{
//			return 0;
//		}
//		vector<int> f(n);
//		vector<int> g(n);
//		f[0] = nums[0];
//		for (int i = 1; i < n; i++)
//		{
//			f[i] = g[i - 1] + nums[i];
//			g[i] = max(f[i - 1], g[i - 1]);
//		}
//		return max(f[n - 1], g[n - 1]);
//
//	}
//};
//
//
//
//// 打家劫舍Ⅱ
//// https://leetcode.cn/problems/house-robber-ii/
//class Solution
//{
//public:
//	int rob(vector<int>& nums)
//	{
//		int n = nums.size();
//		vector<int> f(n);
//		vector<int> g(n);
//		vector<int> f2(n);
//		vector<int> g2(n);
//		if (n == 0)
//		{
//			return 0;
//		}
//		// 偷窃1
//		f[0] = nums[0];
//		if (n == 1)
//		{
//			return f[0];
//		}
//		for (int i = 1; i < n - 1; i++)
//		{
//			f[i] = g[i - 1] + nums[i];
//			g[i] = max(f[i - 1], g[i - 1]);
//		}
//		int ret1 = max(f[n - 2], g[n - 2]);
//		// 不偷窃1
//		f2[1] = nums[1];
//		for (int i = 2; i < n; i++)
//		{
//			f2[i] = g2[i - 1] + nums[i];
//			g2[i] = max(f2[i - 1], g2[i - 1]);
//		}
//		return max(ret1, max(f2[n - 1], g2[n - 1]));
//
//
//	}
//};
//
//
//
//// 删除并获得点数
//// https://leetcode.cn/problems/delete-and-earn/ 
//class Solution
//{
//public:
//	int deleteAndEarn(vector<int>& nums)
//	{
//		int arr[10001] = { 0 };
//		int n = nums.size();
//		for (int i = 0; i < n; i++)
//		{
//			arr[nums[i]] += nums[i];
//		}
//		vector<int> f(10001);
//		vector<int> g(10001);
//		for (int i = 1; i < 10001; i++)
//		{
//			f[i] = g[i - 1] + arr[i];
//			g[i] = max(f[i - 1], g[i - 1]);
//		}
//		return max(f[10000], g[10000]);
//
//	}
//};
//
//
//
//// 粉刷房子
//// https://leetcode.cn/problems/JEj789/
//class Solution
//{
//public:
//	int minCost(vector<vector<int>>& costs)
//	{
//		int n = costs.size();
//		if (n == 1)
//		{
//			return min(costs[0][0], min(costs[0][1], costs[0][2]));
//		}
//		vector<vector<int>> dp(n + 1, vector<int>(3));
//		for (int i = 1; i <= n; i++)
//		{
//			dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
//			dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
//			dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
//
//		}
//		return min(dp[n][0], min(dp[n][1], dp[n][2]));
//
//	}
//};
//
//
//// https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
//class Solution
//{
//	int m, n;
//	int dx[4] = { 0, 0, 1, -1 };
//	int dy[4] = { 1, -1, 0, 0 };
//	int memo[201][201];
//public:
//	int longestIncreasingPath(vector<vector<int>>& matrix)
//	{
//		int ret = 0;
//		m = matrix.size(), n = matrix[0].size();
//		for (int i = 0; i < m; i++)
//			for (int j = 0; j < n; j++)
//			{
//				ret = max(ret, dfs(matrix, i, j));
//			}
//
//		return ret;
//	}
//	int dfs(vector<vector<int>>& matrix, int i, int j)
//	{
//		if (memo[i][j] != 0) return memo[i][j];
//		int ret = 1;
//		for (int k = 0; k < 4; k++)
//		{
//			int x = i + dx[k], y = j + dy[k];
//			if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i]
//				[j])
//			{
//				ret = max(ret, dfs(matrix, x, y) + 1);
//			}
//		}
//		memo[i][j] = ret;
//		return ret;
//	}
//};
//
//
//// 买卖股票的最佳时机冷冻期
//// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
//class Solution {
//public:
//	int maxProfit(vector<int>& prices)
//	{
//		int n = prices.size();
//		vector<vector<int>> dp(n, vector<int>(3));
//		dp[0][0] = -prices[0];
//		for (int i = 1; i < n; i++)
//		{
//			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
//			dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
//			dp[i][2] = dp[i - 1][0] + prices[i];
//		}
//		return max(dp[n - 1][1], dp[n - 1][2]);
//	}
//};
//
//
////买卖股票的最佳时机含手续费
//// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
//class Solution {
//public:
//	int maxProfit(vector<int>& prices, int fee)
//	{
//		int n = prices.size();
//		vector<vector<int>> dp(n, vector<int>(2));
//		dp[0][0] = -prices[0];
//		for (int i = 1; i < n; i++)
//		{
//			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
//			dp[i][1] = max(dp[i - 1][1], dp[i][0] + prices[i] - fee);
//		}
//		return dp[n - 1][1];
//	}
//};



//int main()
//{
//	int n;
//	cin >> n;
//	vector<int> a(n);
//	vector<vector<int>> dp(n, vector<int>(2));
//	int count0 = 0; //女生人数
//	int count1 = 0;//男生人数
//	int Max = INT_MIN;
//	int ret = 0;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> a[i];
//		if (a[i])
//		{
//			count1++;
//			dp[i][1] == count1;
//		}
//		else
//		{
//			dp[i][0] == count0;
//
//		}
//	}
//	for (int i = 0; i < n; i++)
//	{
//		int sum0 = 0, sum1 = 0;
//		int left = i, right = n - 1;
//		while (left < right)
//		{
//			int mid = (left + right) / 2;
//			sum0 = dp[left][0] - dp[right][0];
//			sum1 = dp[left][1] - dp[right][1];
//
//		}
//	}
//	cout << Max;
//	
//	
//	return 0;
//}


//int main()
//{
//	int n;
//	cin >> n;
//	vector<int> a(n);
//
//	int Max = INT_MIN;
//
//	for (int i = 0; i < n; i++)
//	{
//		cin >> a[i];
//	}
//	for (int i = 0; i < n - 1; i++)
//	{
//		int sum0 = 0, sum1 = 0;
//		for (int j = i; j < n; j++)
//		{
//			if (a[j])
//			{
//				sum1++;
//			}
//			else
//			{
//				sum0++;
//			}
//			if (sum1 - sum0 == 0)
//			{
//				Max = max(Max, (j - i + 1));
//			}
//		}
//	}
//	cout << Max;
//
//
//	return 0;
//}
//
//
//
//// 买股票的最佳时机Ⅲ
//// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
//class Solution
//{
//public:
//	int maxProfit(vector<int>& prices)
//	{
//		int n = prices.size();
//		vector<vector<int>> f(n, vector<int>(3, -0x6f6f6f));
//		vector<vector<int>> g(n, vector<int>(3, -0x6f6f6f));
//		f[0][0] = -prices[0], g[0][0] = 0;
//		for (int i = 1; i < n; i++)
//		{
//			for (int j = 0; j < 3; j++)
//			{
//				f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
//				g[i][j] = g[i - 1][j];
//				if (j >= 1)
//				{
//					g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
//				}
//			}
//		}
//		int Max = 0;
//		for (int i = 0; i < 3; i++)
//		{
//			Max = max(Max, g[n - 1][i]);
//		}
//		return Max;
//	}
//};
//
//// 买股票的最佳时机Ⅳ
//// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
//class Solution {
//public:
//	int maxProfit(int k, vector<int>& prices) {
//		int n = prices.size();
//		vector<vector<int>> f(n, vector<int>(k + 1, -0x6f6f6f));
//		vector<vector<int>> g(n, vector<int>(k + 1, -0x6f6f6f));
//		f[0][0] = -prices[0], g[0][0] = 0;
//		for (int i = 1; i < n; i++)
//		{
//			for (int j = 0; j <= k; j++)
//			{
//				f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
//				g[i][j] = g[i - 1][j];
//				if (j >= 1)
//				{
//					g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
//				}
//			}
//		}
//		int Max = 0;
//		for (int i = 0; i <= k; i++)
//		{
//			Max = max(Max, g[n - 1][i]);
//		}
//		return Max;
//	}
//};



//int main()
//{
//    vector<int> nums(3);
//    nums[0] = 5, nums[1] = -3, nums[2] = 5;
//    int n = nums.size();
//    vector<int> f(n + 1);//从前往后
//    vector<int> g(n + 1);//从后往前
//    int sum = 0;
//    int fgmax = INT_MIN;
//    int gmax = INT_MIN;
//    int fmax = INT_MIN;
//    for (int i = 1; i <= n; i++)
//    {
//        sum += nums[i - 1];
//        f[i] = max(f[i - 1] + nums[i - 1], nums[i - 1]);
//        fmax = max(f[i], fmax);
//        g[n - i] = g[n - i + 1] + nums[n - i];
//        gmax = max(gmax, g[n - i]);
//        if (f[i] == sum && sum == fgmax)
//        {
//            fgmax = max(fgmax, max(f[i], f[i] + gmax));
//        }
//    }
//    cout << max(fgmax, fmax);
//	return 0;
//}



// 最大数组和
// https://leetcode.cn/problems/maximum-subarray/
class Solution
{
public:
    int maxSubArray(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n + 1);
        int Max = INT_MIN;
        for (int i = 1; i <= n; i++)
        {
            dp[i] = max(dp[i - 1] + nums[i - 1], nums[i - 1]);
            Max = max(Max, dp[i]);
        }
        return Max;

    }
};


//环形子数组的最大和
// https://leetcode.cn/problems/maximum-sum-circular-subarray/
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n + 1);//最大数组
        vector<int> g(n + 1);//最小数组
        int sum = 0;
        int fmax = INT_MIN, gmin = INT_MAX;
        for (int i = 1; i <= n; i++)
        {
            sum += nums[i - 1];
            f[i] = max(f[i - 1] + nums[i - 1], nums[i - 1]);
            g[i] = min(g[i - 1] + nums[i - 1], nums[i - 1]);
            fmax = max(fmax, f[i]);
            gmin = min(g[i], gmin);
        }
        return sum == gmin ? fmax : max(sum - gmin, fmax);


    }
};


// 乘积最大子数组
// https://leetcode.cn/problems/maximum-product-subarray/
class Solution {
public:
    int maxProduct(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n + 1);
        vector<int> g(n + 1);
        f[0] = g[0] = 1;
        int ret = INT_MIN;
        for (int i = 1; i <= n; i++)
        {
            f[i] = max(nums[i - 1], max(f[i - 1] * nums[i - 1], g[i - 1] * nums[i - 1]));
            g[i] = min(nums[i - 1], min(g[i - 1] * nums[i - 1], f[i - 1] * nums[i - 1]));
            ret = max(ret, f[i]);
        }
        return ret;
    }
};

// 乘积为正数的最长子数组长度
// https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/
class Solution
{
public:
    int getMaxLen(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n + 1);
        vector<int> g(n + 1);
        int ret = INT_MIN;
        for (int i = 1; i <= n; i++)
        {
            if (nums[i - 1] > 0)
            {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            }
            else if (nums[i - 1] < 0)
            {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = max(f[i], ret);
        }
        return ret;
    }
};